class Solution {
public:
    bool canPartition(vector<int>& nums) {
      int len = nums.size();
      int sum = 0;
      for(int i = 0;i < len;i++){
        sum += nums[i];
      }
      if(sum % 2 != 0){
        return false;
      }
      sum /= 2;
      vector<int> dp(sum+1,0);
      for(int i = 0;i < len;i++){
          for(int j = sum;j >= 0;j--){
            if(j >= nums[i]){
              dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
         }
      }
      return dp[sum] == sum;
    }
};
